#include<iostream>
#include<vector>
#include<string>
#include<set>
using namespace std;



 // Definition for singly-linked list.
  struct ListNode {
     int val;
      ListNode *next;
      ListNode(int x) : val(x), next(NULL) {}
  }; 

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        //遍历headA
        set<ListNode*> S;
        ListNode* currA = headA;
        while(currA!=NULL){
            S.insert(currA);
            currA = currA->next;
        }
        ListNode* currB = headB;
        while(currB!=NULL){
            if(S.insert(currB).second==false){
                return currB;
            }
            currB = currB->next;
        }
        return NULL;
    }
};